/**
 * Project Name:javaBaseReview
 * Package Name:com.xuwei.base.queue
 * author:David
 * Date:2015年6月13日下午5:47:41
 * Copyright (c) 2015, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.queue;

import com.xuwei.ext.exception.QueueEmptyException;

/**
 * 队列的顺序存储实现：使用循环数组实现循环队列
 * 
 * @author David
 * @since 2015年6月13日 下午5:47:41
 * @version
 * @since JDK 1.6
 */
public class QueueArray implements Queue {
	private static final int CAP = 7;// 队列默认大小
	private Object[] elements; // 数组元素数组
	private int capacity; // 数组的大小elements.length
	private int front; // 队首指针，指向队首
	private int rear; // 队尾指针，指向队尾一个位置

	public QueueArray(){
		this(CAP);
	}
	
	public QueueArray(int cap) {
		capacity = cap + 1;
		elements = new Object[capacity];
		front = rear = 0;
	}

	@Override
	public int getSize() {
//		return (rear - front + capacity) % capacity;
		return rear-front;
	}

	@Override
	public boolean isEmpty() {
		return front == rear;
	}

	@Override
	public void enqueue(Object e) {
		if (getSize() == capacity - 1) {
			expandSpace();
		}
		elements[rear] = e;
		rear = (rear + 1) % capacity;
	}

	/**
	 * 
	 */
	private void expandSpace() {
		Object[] a = new Object[elements.length * 2];
		int i = front;
		int j = 0;
		// 将从front开始到rear前一个存储单元的元素复制到新数组
		while (i != rear) {
			a[j++] = elements[i];
			i = (i + 1) % capacity;
		}
		elements=a;
		capacity=elements.length;
		front=0;
		rear=j;//设置新的队首、队尾指针
	}

	@Override
	public Object dequeue() throws QueueEmptyException {
		if(isEmpty()){
			throw new QueueEmptyException("错误：队列为空！");
		}
		Object obj=elements[front];
		elements[front]=null;
//		front=(front+1)%capacity;
		front=front+1;
		return obj;
	}

	@Override
	public Object peek() throws QueueEmptyException {
		if(isEmpty()){
			throw new QueueEmptyException("错误：队列为空");
		}
		return elements[front];
	}
	
}
